package leetcode.code0029;

public class Solution2 extends Solution29 {

	@Override
	public int divide(int dividend, int divisor) {
		if (dividend == divisor) {
			return 1;
		}
		int a = dividend > 0 ? add(~dividend, 1) : dividend;
		int b = divisor > 0 ? add(~divisor, 1) : divisor;
		int ans = 0;
		for (int i = 31; i >= 0; i = sub(i, 1)) {
			if ((b >> i) <= a) {
				ans = add(ans, 1 << i);
				a = add(a, -(b << i));
			}
		}
		if ((dividend ^ divisor) < 0) {
			return add(~ans, 1);
		} else {
			return ans;
		}
	}

	public int add(int a, int b) {
		do {
			int carry = (a & b) << 1;
			a = a ^ b;
			b = carry;
		} while (b != 0);
		return a;
	}

	public int sub(int a, int b) {
		return add(a, add(~b, 1));
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
		so.debug7();
	}

}
